package cxydmmszl.chapter02.t019;

/**
 * <li style="color: red;">Prob</li>
 * 将单向链表按某值划分为左边小，中间相等，右边大的形式
 * <li style="color: red;">Desc</li>
 * 给定一个链表，再给定一个整数 pivot，请将链表调整为
 * 左部分都是值小于 pivot 的节点，
 * 中间部分都是值等于 pivot 的节点，
 * 右边部分都是大于 pivot 的节点。
 * 除此之外，对调整后的节点顺序没有更多要求。<br/><br/>
 * <b>输入描述：</b><br/>
 * &emsp;第一行两个整数 n 和 pivot，n 表示链表的长度。<br/>
 * &emsp;第二行 n 个整数 ai 表示链表的节点。<br/><br/>
 * <b>输出描述：</b><br/>
 * &emsp;请在给定的函数内返回链表的头指针。
 * <li style="color: red;">Link</li> CD113
 *
 * @author habitplus
 * @since 2021-08-29 10:24
 */
public class Solution {
    public static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public Node partitionOfLinkedList(Node head, int pivot) {
        if (head == null || head.next == null) {
            return head;
        }

        int cnt = 0;
        Node aux = head;
        while (aux != null) {
            aux = aux.next;
            cnt++;
        }

        Node[] arr = new Node[cnt];
        for (int i = 0; i < cnt; i++) {
            arr[i] = head;
            head = head.next;
        }

        partition(arr, pivot);

        for (int i = 1; i < cnt; i++) {
            arr[i - 1].next = arr[i];
        }
        arr[cnt - 1].next = null;
        return arr[0];
    }

    private void partition(Node[] arr, int pivot) {
        int lt = -1;
        int gt = arr.length;
        int i = 0;
        while (i < gt) {
            if (arr[i].val < pivot)      swap(arr, ++lt, i++);
            else if (arr[i].val > pivot) swap(arr, --gt, i);
            else                         i++;
        }
    }

    private void swap(Node[] arr, int i, int j) {
        if (i == j) return;
        Node t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    /**
     * 不要求顺序的解法
     */
    public Node partitionOfLinkedList01(Node head, int pivot) {
        Node tou = new Node(0);
        Node lt = tou, eq = null, gt = null, nxt, t;

        while (head != null) {
            nxt = head.next;
            head.next = null;
            if (head.val < pivot) { // 在 lt 与 lt.next 之间插入 head
                t = lt.next;
                lt.next = head;
                head.next = t;
                lt = head; // lt 后移到 head
            } else if (head.val > pivot) { // 头插法，gt 始终执行头部
                head.next = gt;
                gt = head;
            } else {
                if (eq == null) {
                    // eq 为空，需要连接 lt 的尾部
                    lt.next = head;
                } else { // 直接尾插
                    eq.next = head;
                }
                eq = head;
            }
            head = nxt;
        }

        if (eq != null) {
            eq.next = gt;
        } else if (tou.next != null) {
            lt.next = gt;
        } else {
            tou.next = gt;
        }

        return tou.next;
    }

    /**
     * 要求顺序的解法
     */
    public Node partitionOfLinkedList02(Node head, int pivot) {
        Node leTou = new Node(0); // <=pivot 的头部空节点
        Node gtTou = new Node(0); // >pivot 的头部空节点
        Node lt = leTou, eq = null, gt = gtTou, nxt, t;

        while (head != null) {
            nxt = head.next;
            head.next = null;
            if (head.val < pivot) { // 在 lt 与 lt.next 之间插入 head
                t = lt.next;
                lt.next = head;
                head.next = t;
                lt = head; // lt 后移到 head
            } else if (head.val > pivot) { // 尾插法，gt 始终指向尾部
                gt.next = head;
                gt = head;
            } else {
                if (eq == null) lt.next = head; // eq 为空，需要连接 lt 的尾部
                else            eq.next = head; // 直接尾插
                eq = head;
            }
            head = nxt;
        }

        // eq != null，直接让 eq 连接大于的那一部分
        if (eq != null)  eq.next = gtTou.next;
        // 小于部分不为空，lt 连接大于的那一部分
        else if (leTou.next != null)  lt.next = gtTou.next;
        // 小于部分和等于部分都为空
        else leTou.next = gtTou.next;

        return leTou.next;
    }
}
